package com.fh.binarysearch;

/**
 * 81. 搜索旋转排序数组 II
 * @author fuhao
 * @date 2025/10/14 21:52
 */
public class T81SearchII {

    class Solution {
        public boolean search(int[] nums, int target) {
            if (nums == null || nums.length == 0) {
                return false;
            }

            int left = 0;
            int right = nums.length - 1;

            while (left <= right) {
                int mid = left + (right - left) / 2; // 防止整数溢出

                // 情况1：找到目标值
                if (nums[mid] == target) {
                    return true;
                }

                // 情况2：无法判断有序区间，收缩边界
                if (nums[left] == nums[mid] && nums[mid] == nums[right]) {
                    left++;
                    right--;
                }
                // 情况3：左半部分有序
                else if (nums[left] <= nums[mid]) {
                    if (nums[left] <= target && target < nums[mid]) {
                        // target 在有序的左半部分
                        right = mid - 1;
                    } else {
                        // target 在无序的右半部分（可能包含旋转点）
                        left = mid + 1;
                    }
                }
                // 情况4：右半部分有序
                else {
                    if (nums[mid] < target && target <= nums[right]) {
                        // target 在有序的右半部分
                        left = mid + 1;
                    } else {
                        // target 在无序的左半部分（可能包含旋转点）
                        right = mid - 1;
                    }
                }
            }
            // 循环结束仍未找到
            return false;
        }
    }
}
